/*
https://leetcode.cn/problems/construct-target-array-with-multiple-sums/solution/duo-ci-qiu-he-gou-zao-mu-biao-shu-zu-by-leetcode-s/
 */
import java.util.PriorityQueue;

public class Solution1354 {
    public boolean isPossible(int[] target) {
        if (target.length==1){
            return target[0]==1;
        }
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>((a,b)->b-a);
        long sum=0;
        for (int i : target) {
            priorityQueue.offer(i);
            sum+=i;
        }
        while (true){
            int x=priorityQueue.poll();
            if (x==1){
                return true;
            }
            if (x*2-sum<1){
                return false;
            }
            long tt=sum-x;
            int y=priorityQueue.peek();
            long k=y==1?(sum-y-1)/(sum-x):(x-y)/(sum-x)+1;
            if (x-k*tt<=0){
                return false;
            }
            x-=k*tt;
            sum-=k*tt;
            priorityQueue.offer(x);
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution1354().isPossible(new int[]{2,900000002}));
    }
}
